package com.lfg.leetcode.leetcode300;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class No460LFUCache {
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(10);
        String[] opList = new String[]{"put", "put", "put", "put", "put", "get", "put", "get", "get", "put", "get", "put", "put", "put", "get", "put", "get", "get", "get", "get", "put", "put", "get", "get", "get", "put", "put", "get", "put", "get", "put", "get", "get", "get", "put", "put", "put", "get", "put", "get", "get", "put", "put", "get", "put", "put", "put", "put", "get", "put", "put", "get", "put", "put", "get", "put", "put", "put", "put", "put", "get", "put", "put", "get", "put", "get", "get", "get", "put", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "get", "get", "get", "put", "put", "put", "get", "put", "put", "put", "get", "put", "put", "put", "get", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "put", "put", "put"};
        int[][] data = new int[][]{{10, 13}, {3, 17}, {6, 11}, {10, 5}, {9, 10}, {13}, {2, 19}, {2}, {3}, {5, 25}, {8}, {9, 22}, {5, 5}, {1, 30}, {11}, {9, 12}, {7}, {5}, {8}, {9}, {4, 30}, {9, 3}, {9}, {10}, {10}, {6, 14}, {3, 1}, {3}, {10, 11}, {8}, {2, 14}, {1}, {5}, {4}, {11, 4}, {12, 24}, {5, 18}, {13}, {7, 23}, {8}, {12}, {3, 27}, {2, 12}, {5}, {2, 9}, {13, 4}, {8, 18}, {1, 7}, {6}, {9, 29}, {8, 21}, {5}, {6, 30}, {1, 12}, {10}, {4, 15}, {7, 22}, {11, 26}, {8, 17}, {9, 29}, {5}, {3, 4}, {11, 30}, {12}, {4, 29}, {3}, {9}, {6}, {3, 4}, {1}, {10}, {3, 29}, {10, 28}, {1, 20}, {11, 13}, {3}, {3, 12}, {3, 8}, {10, 9}, {3, 26}, {8}, {7}, {5}, {13, 17}, {2, 27}, {11, 15}, {12}, {9, 19}, {2, 15}, {3, 16}, {1}, {12, 17}, {9, 1}, {6, 19}, {4}, {5}, {5}, {8, 1}, {11, 7}, {5, 2}, {9, 28}, {1}, {2, 2}, {7, 4}, {4, 22}, {7, 24}, {9, 26}, {13, 28}, {11, 26}};

        for (int i = 0; i < opList.length; i++) {
            String op = opList[i];
            int[] param = data[i];
            if (op.equals("put")) {
                cache.put(param[0], param[1]);
                System.out.print("null   ");
            } else if (op.equals("get")) {
                System.out.print(param[0] + "= " + cache.get(param[0]) + "   ");
            }
        }

    }

}

class LFUCache {

    Map<Integer, LFUNode> data = null;
    Map<Integer, LinkedList<LFUNode>> cntMap = null;
    int capacity = 0;
    int index = 1;
    int size = 0;


    public LFUCache(int capacity) {
        this.capacity = capacity;
        data = new HashMap<>(capacity);
        cntMap = new HashMap<>(capacity);
    }

    public int get(int key) {
        LFUNode v = data.get(key);
        if (v == null) {
            return -1;
        }
        addCnt(v);
        return v.value;
    }

    private void addCnt(LFUNode v) {
        int cnt = v.cnt;
        LinkedList<LFUNode> list = cntMap.get(cnt);
        list.remove(v);
        if (list.isEmpty()) {
            cntMap.remove(cnt);
            if(cnt == index){
                index++;
            }
        }
        v.cnt = v.cnt + 1;
        LinkedList<LFUNode> l = cntMap.get(v.cnt);
        if (l == null) {
            l = new LinkedList<>();
            cntMap.put(v.cnt, l);
        }
        l.addFirst(v);
    }

    public void put(int key, int value) {
        LFUNode v = data.get(key);
        if (v != null) {
            v.value = value;
            addCnt(v);
            return;
        }
        v = new LFUNode();
        v.cnt = 1;
        v.value = value;
        v.key = key;
        data.put(key, v);
        size++;
        LinkedList<LFUNode> list = cntMap.get(v.cnt);
        if (list == null) {
            list = new LinkedList<>();
            cntMap.put(v.cnt, list);
        }
        list.addFirst(v);

        if (size > capacity) {
            list = cntMap.get(index);
            LFUNode node = list.removeLast();
            data.remove(node.key);
            if (list.isEmpty()) {
                cntMap.remove(index);
            }
            size--;
        }
        index = 1;
    }
}

class LFUNode {
    public int key;
    public int value;
    public int cnt;

}
